␈↓␈↓↓␈↓α␈↓β␈↓∧␈↓␈↓ ελRECURSION

␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃The␈α
term␈α
recursion␈α
refers␈α
to␈α
several␈α
related␈α
concepts␈α
in␈α
computer␈α
science␈α
and␈α
mathematics.

␈↓ ↓H

␈↓ ↓H
Recursion relation
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃One␈α∞or␈α∞more␈α∞functions␈α∞of␈α∞an␈α∞integer␈α∞variable␈α∞is␈α∞defined␈α
by␈α
giving␈α
initial␈α
values␈α
and␈α
by␈α
giving␈α
the
␈↓ ↓Hvalue␈αfor␈αlarger␈αintegers␈α
in␈α
terms␈α
of␈α
smaller␈α
ones.␈α
No␈α
single␈α
definition␈α
is␈α
generally␈α
accepted,␈α
so␈α
we␈α
shall␈α
give
␈↓ ↓Hexamples␈α
of␈α
increasing␈α
complexity.

␈↓ ↓H
	1. The Fibonacci sequence is given by the equations
␈↓ ↓H

␈↓ ↓H
        ␈↓↓f␈↓α0␈↓↓ = 1
␈↓ ↓H

␈↓ ↓H
        f␈↓α1␈↓↓ = 1
␈↓ ↓H

␈↓ ↓H
        f␈↓αn+1␈↓↓ = f␈↓αn␈↓↓ + f␈↓αn-1.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃2.␈α
When␈α
differential␈α
equations␈α
are␈α
to␈α
be␈α
solved␈α
numerically,␈α
recursion␈α
relations␈α
such␈α
as

␈↓ ↓H
     ␈↓↓f(x␈↓α0␈↓↓ + nh) = F(f(x␈↓α0␈↓↓ + (n-1)h) , f(x␈↓α0␈↓↓ + (n-2)h) , . . . , f(x␈↓α0␈↓↓ + (n-k)h))␈↓
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
arise where ␈↓↓f␈↓  is in general a vector of real numbers.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃3.␈α
When␈α
linear␈α
differential␈α
equations␈α
are␈α
solved␈α
by␈α
series,␈α
recursion␈αrelations␈αfor␈αthe␈αcoefficients␈αof
␈↓ ↓Hthe␈α
powers␈α
of␈α
the␈α
independent␈α
variables␈α
arise.

␈↓ ↓H
Recursive functions
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃The␈α⊃systematic␈α⊃study␈α⊃of␈α⊃recursion␈α⊃began␈α⊃in␈α⊃the␈α⊃1920's␈α⊃when␈α⊃mathematical␈α⊃logic␈α⊂began␈α⊂to␈α⊂treat
␈↓ ↓Hquestions␈αof␈αdefinability,␈αcomputability␈αand␈αdecidability.␈αAn␈αimportant␈αrole␈αis␈αplayed␈αby␈αprimitive␈αrecursive
␈↓ ↓Hfunctions␈α
defined␈α
as␈α
follows:

␈↓ ↓H
	a. Integer constants are primitive recursive.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃b.␈α
␈↓↓x␈↓αi␈↓␈α
is␈α
a␈α
primitive␈α
recursive␈α
function␈α
of␈α
a␈α
set␈α
of␈α
arguments␈α
including␈α
␈↓↓x␈↓αi␈↓.

␈↓ ↓H
	c. Addition and multiplication are primitive recursive.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃d.␈α
Functions␈α
obtained␈α
from␈α
primitiver␈α
recursive␈α
functions␈α
by␈α
composition␈α
are␈α
primitive␈α
recursive.

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃e.␈αIf␈↓↓g␈↓␈αand␈α␈↓↓h␈↓␈αare␈αprimitive␈αrecursive␈αfunctions␈α
of␈α
␈↓↓n-1␈α
␈↓and␈α
␈↓↓n+1␈↓␈α
arguments␈α
respectively,␈α
and␈α
␈↓↓f␈↓␈α
is␈α
defined
␈↓ ↓Hby␈α
the␈α
relations

␈↓ ↓H
        ␈↓↓f(0 , x␈↓α2␈↓↓ , . . . , x␈↓αn␈↓↓ = g(x␈↓α2␈↓↓ , . . . , x␈↓αn␈↓↓)
␈↓ ↓H

␈↓ ↓H
	f(x␈↓α1␈↓↓ + 1, x␈↓α2␈↓↓ , . . . ,  ␈↓αn␈↓↓) = h(f(x␈↓α1␈↓↓ , . . . , x␈↓αn␈↓↓) , . . . , x␈↓αn␈↓↓n) ,␈↓
␈↓ ↓H

␈↓ ↓H
then ␈↓↓f␈↓ is primitive recursive.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃g.␈α
A␈α
function␈α
is␈α
primitive␈α
recursive␈α
only␈α
if␈α
it␈α
follows␈α
from␈α
the␈α
previous␈α
rules␈α
that␈α
it␈α
is.

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃All␈α∩the␈α∩common␈α⊃functions␈α⊃of␈α⊃number␈α⊃theory␈α⊃are␈α⊃primitive␈α⊃recursive.␈α⊃Moreover,␈α⊃many␈α⊃important
␈↓ ↓Hfunctions␈αon␈αother␈αcountable␈αdomains␈αthan␈αthe␈αintegers␈α
correspond␈α
to␈α
primitive␈α
recursive␈α
functions␈α
when␈α
we
␈↓ ↓Hchoose␈α
a␈α
specific␈α
enumeration␈α
for␈α
the␈α
domain.

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃Primitive␈α∞recursive␈α∞functions␈α∞are␈α∞a␈α∞proper␈α∞subset␈α∞of␈α∞general␈α∞recursive␈α∞functions.␈α
The␈α
definition␈α
of
␈↓ ↓Hgeneral␈α∩recursive␈α∩function␈α∩is␈α∩like␈α∩that␈α∩given␈α∩above␈α∩for␈α∩primitive␈α∩recursive␈α⊃functions␈α⊃except␈α⊃that␈α⊃the
␈↓ ↓Hrelations␈α␈↓∧E␈↓␈αare␈αreplaced␈αby␈αan␈αarbitrary␈αfinite␈αcollection␈α
of␈α
equations␈α
relating␈α
the␈α
values␈α
of␈α
␈↓↓f␈↓␈α
for␈α
different
␈↓ ↓Harguments,␈α
and␈α
the␈α
function␈α
is␈α
considered␈α
defined␈α
␈↓βif␈α
and␈α
only␈α
if␈↓␈α
a␈α
unique␈α
value␈α
of␈α
␈↓↓f(x␈↓α1␈↓↓␈α,␈α.␈α.␈α.␈α,␈αx␈↓αn␈↓↓)␈↓␈αcan␈αbe
␈↓ ↓Hdeduced␈αfrom␈αthe␈αequations␈αfor␈αeach␈α␈↓↓n␈↓-tuplet␈α␈↓↓(x␈↓α1␈↓↓␈α,␈α.␈α.␈α.␈α,␈αx␈↓αn␈↓↓)␈↓.␈αNaturally,␈αif␈αsomeone␈αgives␈αyou␈αan␈αarbitrary
␈↓ ↓Hcollection␈α⊃of␈α⊃such␈α⊃relations,␈α⊃you␈α⊃may␈α⊃not␈α⊃be␈α⊃able␈α⊃to␈α⊃determine␈α⊃whether␈α⊃␈↓↓f(x␈↓α1␈↓↓␈α⊃,␈α⊃.␈α⊃.␈α⊃.␈α⊃,␈α⊂x␈↓αn␈↓↓)␈↓␈α⊂is␈α⊂uniquely
␈↓ ↓Hdetermined,␈α
so␈α
you␈αmay␈αnot␈αknow␈αwhether␈αyou␈αhave␈αa␈αgeneral␈αrecursive␈αfunction␈αor␈αnot.␈αThis␈αdifficulty␈αis
␈↓ ↓Hunavoidable.␈αThere␈αis␈αno␈αway␈αto␈αgive␈αa␈αdefinition␈αscheme␈αthat␈αis␈αalways␈αguaranteed␈αto␈αgive␈αa␈αfunction␈αbut
␈↓ ↓Hwhich␈α
will␈α
give␈α
all␈α
computable␈α
functions.␈α
This␈α
fact␈α
is␈α
itself␈α
expressed␈α
in␈αrecursive␈αfunction␈αtheory␈αby␈αthe
␈↓ ↓Hstatement␈α∞that␈α∞the␈α∞set␈α∞of␈α∞computable␈α∞functions␈α∞is␈α∞recursively␈α∞enumerable␈α∞but␈α
not␈α
recursive.␈α
It␈α
was␈α
first
␈↓ ↓Hproved␈α
by␈α
Turing.

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃An␈α
important␈α
result␈α
for␈α
computer␈α
science␈αis␈αthat␈αthe␈αgeneral␈αrecursive␈αfunctions␈αco-incide␈αwith␈αthe
␈↓ ↓Hfunctions␈α
defined␈α
by␈α
Turing␈α
machines␈α
which␈α
are␈α
a␈α
simple␈α
form␈α
of␈α
computer.␈αThey␈αalso␈αco-incide␈αwith␈αthe
␈↓ ↓Hfunctions␈α⊂of␈α⊂integers␈α⊂defined␈α⊂by␈α⊂Algol␈α⊂or␈α⊂Fortran␈α⊂programs␈α⊂assuming␈α⊂that␈α⊂the␈α⊂program␈α∂can␈α∂cope␈α∂with
␈↓ ↓Hwhatever␈α
size␈α
integers␈α
arise.

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃The␈α
study␈α
of␈α
computable␈α
functions␈α
is␈α
the␈α
domain␈α
of␈α
recursive␈α
function␈α
theory,␈α
an␈αactive␈αbranch␈αof
␈↓ ↓Hmathematics.␈αThe␈αconnection␈αbetween␈αcurrent␈αresearch␈αin␈αrecursive␈αfunction␈αtheory␈αand␈αcomputing␈αpractice
␈↓ ↓Hor␈α∂even␈α∂current␈α∂research␈α∂in␈α∞computer␈α∞science␈α∞is␈α∞rather␈α∞tenuous.␈α∞This␈α∞situation␈α∞might␈α∞change␈α∞because␈α∞of
␈↓ ↓Hdevelopments␈α
in␈α
either␈α
field.

␈↓ ↓H

␈↓ ↓H
Recursive procedures
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃In␈αprogramming,␈αit␈αis␈αfrequently␈αconvenient␈αto␈αhave␈αa␈αprocedure␈αuse␈αitself␈αas␈αa␈αsubprocedure.␈αIf␈αthe
␈↓ ↓Hprocedure␈α∩does␈α∩this,␈α⊃it␈α⊃is␈α⊃called␈α⊃recursive.␈α⊃As␈α⊃far␈α⊃as␈α⊃programming␈α⊃languages␈α⊃are␈α⊃concerned,␈α⊃recursive
␈↓ ↓Hprocedures␈α∂are␈α∂quite␈α∂natural;␈α∂it␈α∂requires␈α∞a␈α∞special␈α∞statement␈α∞in␈α∞the␈α∞definition␈α∞of␈α∞the␈α∞language␈α∞to␈α∞forbid
␈↓ ↓Hthem.␈α⊃However,␈α⊃implementing␈α⊃them␈α⊃requires␈α⊃that␈α⊃a␈α⊃special␈α⊃kind␈α⊃of␈α⊃object␈α⊂code␈α⊂be␈α⊂compiled,␈α⊂and␈α⊂early
␈↓ ↓Hprogramming␈α∀languages␈α∀like␈α∀FORTRAN␈α∀don't␈α∀do␈α∀it.␈α∀The␈α∀problem␈α∪is␈α∪that␈α∪variables␈α∪in␈α∪the␈α∪program
␈↓ ↓Hcorrespond␈α∂to␈α∂locations␈α∂in␈α∞the␈α∞machine,␈α∞and␈α∞when␈α∞the␈α∞program␈α∞is␈α∞called␈α∞by␈α∞itself,␈α∞it␈α∞will␈α∞use␈α∞these␈α∞same
␈↓ ↓Hlocations␈αforgetting␈αtheir␈αprevious␈αcontents.␈αTherefore,␈αrecursive␈αprograms␈αuse␈αan␈αarray␈αcalled␈αthe␈αstack␈αto
␈↓ ↓Hstore␈αthe␈αcontents␈αof␈αregisters␈αthat␈αmust␈αbe␈α
saved.␈α
This␈α
storage␈α
can␈α
be␈α
done␈α
by␈α
the␈α
calling␈α
routine␈α
before␈α
it
␈↓ ↓Henters␈αthe␈αsubroutine␈αor␈αit␈αcan␈α
be␈α
done␈α
by␈α
the␈α
subroutine␈α
before␈α
it␈α
uses␈α
the␈α
registers,␈α
the␈α
latter␈α
being␈α
more
␈↓ ↓Hcommon.␈α∂After␈α∂the␈α∂registers␈α∂have␈α∂been␈α∂saved␈α∂on␈α∞the␈α∞stack,␈α∞the␈α∞index␈α∞into␈α∞the␈α∞stack␈α∞is␈α∞increased␈α∞by␈α∞the
␈↓ ↓Hnumber␈α⊂of␈α⊂registers␈α⊂stored␈α⊂so␈α⊂that␈α⊂subsequent␈α⊂saving␈α⊂on␈α⊂the␈α⊂stack␈α⊂will␈α⊂have␈α⊂a␈α⊂fresh␈α⊂place.␈α⊂When␈α∂the
␈↓ ↓Hsubroutine␈αexits␈αthe␈α
contents␈α
of␈α
the␈α
saved␈α
registers␈α
are␈α
restored␈α
from␈α
the␈α
stack␈α
to␈α
their␈α
previous␈α
values␈α
and
␈↓ ↓Hthe␈αstack␈αpointer␈αis␈αreduced␈αby␈αthe␈αamount␈αit␈αwas␈αpreviously␈αincreased.␈αThis␈αis␈α
done␈α
by␈α
the␈α
caller␈α
or␈α
by␈α
the
␈↓ ↓Hsubroutine␈αaccording␈αto␈αwhether␈αthe␈αcaller␈αor␈αsubroutine␈αdid␈αthe␈αoriginal␈αstoring.␈αAn␈αalternative␈αtechnique
␈↓ ↓His␈αto␈αuse␈αthe␈αstack␈αfor␈αall␈αtemporary␈αregisters.␈αIn␈αthis␈αcase,␈αit␈αis␈αunnecessary␈αto␈αmove␈αdata␈αaround␈αand␈αit␈αis
␈↓ ↓Honly␈α
necessary␈α
to␈αchange␈αthe␈αstack␈αpointer␈αwhen␈αsubroutines␈αare␈αentered␈αand␈αleft.␈αHowever,␈αthis␈αtechnique
␈↓ ↓Huses␈α
up␈α
the␈α
indexing␈α
capabilities␈α
of␈α
some␈α
machines␈α
which␈α
may␈α
be␈α
wanted␈α
for␈α
other␈α
purposes.

␈↓ ↓H␈α?␈α⊃Recursive␈α⊂programs␈α⊂can␈α⊂be␈α⊂written␈α⊂in␈α⊂any␈α⊂programming␈α⊂language␈α⊂by␈α∂explicitly␈α∂programming␈α∂the
␈↓ ↓Hsaving␈αand␈αrestoring.␈αHowever,␈αsome␈αlanguages,␈αe.g.␈αFORTRAN,␈αuse␈αtermporary␈αregisters␈αnot␈αaddressable␈αin
␈↓ ↓Hthe␈α
language␈α
so␈α
he␈α
can't␈α
arrange␈α
for␈α
their␈α
saving␈αand␈αrestoration␈αand␈αmust␈αlimit␈αhimself␈αto␈αprograms␈αnot
␈↓ ↓Husing␈αsuch␈αregisters.␈αIn␈αFORTRAN␈αthis␈αmeans␈αgiving␈αup␈αthe␈αFORTRAN␈αsubroutine␈αmechanism␈αand␈αgiving
␈↓ ↓Hup␈α
DO␈α
statements.

␈↓ ↓H␈α?␈α⊃The␈αfirst␈αlanguage␈αto␈αuse␈α
recursive␈α
subroutines␈α
on␈α
a␈α
regular␈α
basis␈α
were␈α
the␈α
IPL␈α
languages␈α
of␈α
Newell,
␈↓ ↓HShaw␈α∂and␈α∂Simon.␈α∂Lists␈α∂were␈α∞used␈α∞for␈α∞the␈α∞stack␈α∞and␈α∞the␈α∞saving␈α∞and␈α∞restoring␈α∞was␈α∞done␈α∞explicitly␈α∞by␈α∞the
␈↓ ↓Hprogrammer.

␈↓ ↓H␈α?␈α⊃The␈α
first␈α
language␈α
provide␈α
an␈α
automatic␈α
mechanism␈α
for␈α
recursion␈α
was␈α
LISP.

␈↓ ↓H␈α?␈α⊃Algol␈α
60␈α
and␈α
its␈α
successors␈α
allow␈α
recursion.

␈↓ ↓H␈α?␈α⊃Many␈αcomputers␈αhave␈αspecial␈αinstruction␈αfor␈αhandling␈αstacks,␈αe.g.␈αthe␈αPUSH␈αand␈αPOP␈αinstructions␈αof
␈↓ ↓Hthe␈α
Digital␈α
Equipment␈α
PDP-10.␈α
Other␈α
machines␈α
such␈α
as␈α
the␈α
Burroughs␈α
6500␈α
have␈α
instructions␈α
that␈αuse␈αa
␈↓ ↓Hhardware␈α∩stack␈α∩directly.␈α∩These␈α∩special␈α∩facilities␈α∩give␈α∩a␈α∩modest␈α∩increase␈α⊃in␈α⊃the␈α⊃efficiency␈α⊃of␈α⊃recursive
␈↓ ↓Hprogramming.

␈↓ ↓H

␈↓ ↓H
Recursive conditional expressions
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃The␈αrecursive␈αuse␈αof␈αconditional␈αexpressions␈αprovides␈αan␈α
economical␈α
way␈α
of␈α
getting␈α
the␈α
functions␈α
that
␈↓ ↓Hare␈α∪computable␈α∪in␈α∩terms␈α∩of␈α∩a␈α∩collection␈α∩of␈α∩base␈α∩functions.␈α∩This␈α∩technique␈α∩is␈α∩the␈α∩basis␈α∩of␈α∩the␈α∩LISP
␈↓ ↓Hprogramming␈α∩language␈α∩and␈α∩also␈α∩of␈α⊃the␈α⊃theoretical␈α⊃system␈α⊃of␈α⊃D.␈α⊃Scott␈α⊃for␈α⊃studying␈α⊃the␈α⊃properties␈α⊃of
␈↓ ↓Hcomputer␈α
programs.

␈↓ ↓H
	A conditional expression has the form, in Algol notation, of
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
        ␈↓βif ␈↓↓p ␈↓βthen ␈↓↓a ␈↓βelse ␈↓↓b␈↓.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HIt␈αis␈αevaluated␈αby␈αfirst␈αevaluating␈αthe␈αpropositional␈αexpression␈α␈↓↓p␈↓.␈αIf␈α␈↓↓p␈↓␈αis␈α␈↓βtrue␈↓,␈αthe␈αvalue␈αof␈αthe␈αconditional
␈↓ ↓Hexpression␈αis␈αthat␈αof␈α␈↓↓a␈↓,␈αand␈αif␈αthe␈αvalue␈αof␈α␈↓↓p␈↓␈αis␈α␈↓βfalse␈↓,␈αthe␈αvalue␈αof␈αthe␈α
conditional␈α
expression␈α
is␈α
that␈α
of␈α
␈↓↓b␈↓.␈α
It
␈↓ ↓His␈α
important␈α
to␈α
note␈α
that␈α
only␈α
one␈α
of␈α
␈↓↓a␈↓␈α
or␈α
␈↓↓b␈↓␈α
is␈α
actually␈α
evaluated.

␈↓ ↓H␈α?␈α⊃A␈α
simple␈α
example␈α
of␈α
the␈α
use␈α
of␈α
conditional␈α
expressions␈α
is␈α
to␈α
define␈α
the␈α
absolute␈α
value␈α
of␈α
a␈α
number␈α
by

␈↓ ↓H
	␈↓↓|x| = ␈↓βif␈↓↓ x < 0 ␈↓βthen␈↓↓ -x ␈↓βelse␈↓↓ x.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃Conditional␈α
expressions␈α
are␈α
used␈α
to␈α
define␈α
functions␈α
recursively␈α
by␈α
writing␈α
the␈α
definition␈α
in␈α
the␈α
form

␈↓ ↓H
       	␈↓↓f(x , . . . , z) ← ␈↓∧E␈↓↓{x , . . . , z, f , g , . . . , h}␈↓,
␈↓ ↓H

␈↓ ↓H
␈↓ ↓Hwhere␈α
␈↓∧E␈↓␈α
is␈α
an␈α
expression␈α
involving␈α
the␈α
variables,␈↓↓x␈α
,␈α
.␈α
.␈α
.␈α
,␈α
z␈↓,␈α
the␈α
function␈α␈↓↓f␈↓␈αbeing␈αdefined,␈αand␈αknown␈αor
␈↓ ↓Hpreviously␈α
defined␈α
functions␈α
␈↓↓g␈α
,␈α
.␈α
.␈α
.␈α
,␈α
h␈↓.

␈↓ ↓H␈α?␈α⊃An␈α
example␈α
of␈α
such␈α
a␈α
definition␈α
is

␈↓ ↓H
	␈↓↓n! ← ␈↓βif␈↓↓ n = 0 ␈↓βthen␈↓↓ 1 ␈↓βelse␈↓↓ n.(n-1)!␈↓.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈α?␈α⊃The␈αgeneral␈αmethod␈αfor␈αevaluating␈αrecursive␈αconditional␈αexpressions␈αis␈αillustrated␈αby␈αusing␈αthe␈α
above
␈↓ ↓Hdefinition␈α
to␈α
evaluate␈α
3!.␈α
Namely,␈α
we␈α
have

␈↓ ↓H
        3! = ␈↓βif␈↓↓ 3=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓3.(3-1)!
␈↓ ↓H
       	   = 3.2! =3.(␈↓βif␈↓↓ 2=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓2.(2-1)!)
␈↓ ↓H
	   = 3.2.(␈↓βif ␈↓↓1=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓1.(1-1)!)
␈↓ ↓H
	   = 3.2.1.(␈↓βif ␈↓↓0=0 ␈↓βthen ␈↓↓1 ␈↓βelse ␈↓↓0.(0-1)!)
␈↓ ↓H
	   = 3.2.1.1 = 6.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HNote␈α⊂that␈α⊂the␈α⊂rule␈α⊂for␈α⊂evaluating␈α⊂conditional␈α⊂expressions␈α⊂ensures␈α⊂that␈α⊂(-1)!␈α⊂is␈α∂never␈α∂evaluated.␈α∂This␈α∂is
␈↓ ↓Hnecessary␈α
since␈α
its␈α
evaluation␈α
wouldn't␈α
terminate.␈α
Several␈α
points␈α
should␈α
be␈α
noted.

␈↓ ↓H␈α?␈α⊃First,␈α∪in␈α∪a␈α∪programming␈α∩language␈α∩that␈α∩uses␈α∩recursive␈α∩conditional␈α∩expressions,␈α∩3!␈α∩would␈α∩not␈α∩be
␈↓ ↓Hevaluated␈αby␈αthe␈αabove␈αsymbolic␈αmanipulation.␈αEither␈α␈↓↓(a)␈↓␈αwould␈αbe␈αcompiled␈α
into␈α
a␈α
recursive␈α
subroutine␈α
(i.e.
␈↓ ↓Ha␈αsubroutine␈αof␈αthe␈αtype␈αexplained␈αabove␈αthat␈αcalls␈αitself␈αand␈αuses␈αa␈αstack␈αto␈αsave␈αintermediate␈αresults␈αand
␈↓ ↓Hreturn␈α
addresses)␈α
or␈α
a␈α
recursive␈α
interpreter␈α
would␈α
interpret␈α
a␈α
list␈α
structure␈α
version␈α
of␈α
␈↓↓(a)␈↓.

␈↓ ↓H␈α?␈α⊃Second,␈α␈↓↓(a)␈↓␈αcan␈αeasily␈αbe␈αreplaced␈αby␈αanother␈αexpression␈αfor␈αthe␈αfactorial␈αthat␈αcan␈αbe␈αcompiled␈αinto␈αa
␈↓ ↓Hnon-recursive␈α
program.␈α
Namely,␈α
we␈α
write

␈↓ ↓H
	␈↓↓n! ← fact(n, 0, 1)␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
	␈↓↓fact(n, m, p) ← ␈↓βif␈↓↓ m = n ␈↓βthen ␈↓↓p ␈↓βelse ␈↓↓fact(n, m+1,(m+1)p).
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H(b)␈α
␈↓can␈α
be␈α
translated␈α
into␈α
a␈αnon-recursive␈αprogram,␈αbecause␈αthe␈αonly␈αoccurrence␈αof␈αfact␈αon␈αthe␈αright␈αhand
␈↓ ↓Hside␈α⊂of␈α∂the␈α∂definition␈α∂is␈α∂at␈α∂the␈α∂outer␈α∂level,␈α∂i.e.␈α∂␈↓↓fact(n,␈α∂m+1,(m+1)p)␈↓␈α∂gives␈α∂the␈α∂value␈α∂of␈α∂␈↓↓fact(n,␈α∂m,␈α∂p)␈α∂␈↓in
␈↓ ↓Hcontrast␈αto␈αthe␈αthe␈αsituation␈αin␈α␈↓↓(a)␈α␈↓where␈α␈↓↓(n-1)!␈α␈↓must␈αbe␈αmultiplied␈αby␈α␈↓↓n␈α␈↓to␈αgive␈α␈↓↓n!.␈α␈↓This␈αallows␈αthe␈αobject
␈↓ ↓Hprogram␈α∂to␈α∂contain␈α∂an␈α∂ordinary␈α∂jump␈α∂to␈α∂itself␈α∂rather␈α∂than␈α∂a␈α∞subroutine␈α∞call.␈α∞When␈α∞this␈α∞is␈α∞possible,␈α∞the
␈↓ ↓Hfunction␈αdefinition␈αis␈αcalled␈αiterative.␈αThus␈αfact␈α
is␈α
iterative␈α
while␈α
the␈α
␈↓↓(a)␈α
␈↓is␈α
not.␈α
Recursive␈α
definitions␈α
cannot
␈↓ ↓Hin␈α
general␈α
be␈α
replaced␈α
by␈α
iterative␈α
definitions␈α
except␈α
by␈α
encoding␈α
the␈α
stack␈α
as␈α
a␈α
variable␈α
in␈α
the␈αprogram,
␈↓ ↓Hand␈α
if␈α
this␈α
has␈α
to␈α
be␈α
done␈α
there␈α
is␈α
no␈α
advantage␈α
in␈α
the␈α
replacement.

␈↓ ↓H␈α?␈α⊃Third,␈αthere␈αmay␈αbe␈αseveral␈αoccurrences␈αof␈αthe␈αfunction␈αbeing␈αdefined␈αon␈αthe␈αright␈αhand␈αside␈αof␈αthe
␈↓ ↓Hrecursive␈α∞definition,␈α∞and␈α∞whether␈α∞the␈α∞evaluation␈α∞terminates␈α∞may␈α∞depend␈α
on␈α
which␈α
occurrence␈α
is␈α
evaluated
␈↓ ↓Hfirst.␈α
The␈α
following␈α
example␈α
due␈α
to␈α
Morris␈α
shows␈α
this:

␈↓ ↓H
	␈↓↓f(x,y) ← ␈↓βif ␈↓↓x=0 ␈↓βthen ␈↓↓0 ␈↓βelse ␈↓↓f(x-1 , f(y-2, x)).␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HThe␈α∞reader␈α∞should␈α∞evaluate␈α∞␈↓↓f(2,1)␈↓␈α∞to␈α
convince␈α
himself␈α
of␈α
this.␈α
J.␈α
M.␈α
Cadiou␈α
has␈α
given␈α
rules␈α
that␈α
give␈α
the
␈↓ ↓H"least␈α
fixed␈α
point"␈α
of␈α
the␈α
definition␈α
regarded␈α
as␈α
a␈α
functional␈α
equation.

␈↓ ↓H␈α?␈α⊃It␈αis␈αalso␈αpossible␈αto␈αuse␈αrecursive␈αconditional␈αexpressions␈αto␈αdefine␈αfunctions␈αthat␈αtake␈αfunctions␈αas
␈↓ ↓Harguments␈α⊃or␈α⊃give␈α⊃functions␈α⊂as␈α⊂results.␈α⊂However,␈α⊂there␈α⊂remain␈α⊂unsolved␈α⊂problems␈α⊂in␈α⊂getting␈α⊂compiling
␈↓ ↓Halgorithms␈α
that␈α
give␈α
efficient␈α
object␈α
code␈α
and␈α
give␈α
the␈α
"right"␈α
answers␈α
in␈α
all␈α
cases.

␈↓ ↓H